import java.util.ArrayList;
import java.util.List;

/**
 * @author shuang
 * @date 2022/5/2 12:10
 * 980. 不同路径 III
 * https://leetcode-cn.com/problems/unique-paths-iii/
 */
public class Solutions_980 {
    public static void main(String[] args) {
        int[][] grid1 = {{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 2, -1}};  // output: 2
        int[][] grid2 = {{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 2}};  // output: 4
        int[][] grid3 = {{0, 1}, {2, 0}};  // output: 0

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(grid1);
        inputs.add(grid2);
        inputs.add(grid3);

        Solutions_980 obj = new Solutions_980();
        for (int[][] input : inputs) {
            int result = obj.uniquePathsIII(input);
            System.out.println(result);
        }
    }

    private int rows;
    private int cols;

    /**
     * 1、找到起点位置
     * 2、记录下能够走到的位置总数
     * 3、DFS 查找不同路径
     * 4、走过的地方标记为 -1
     * 5、走完后，当前位置还原为 0
     * @param grid
     * @return
     */
    private int uniquePathsIII(int[][] grid) {
        rows = grid.length;
        cols = grid[0].length;
        int startRow = -1;
        int startCol = -1;
        int stepCnt = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == -1) {
                    continue;
                }
                stepCnt ++;
                if (grid[i][j] == 1) {
                    startRow = i;
                    startCol = j;
                }
            }
        }
        // 已经位于 grid[startRow][startCol]，则步数已经减 1
        int res = dfs(grid, startRow, startCol, stepCnt - 1);
        return res;
    }

    private int dfs(int[][] grid, int i, int j, int stepCnt) {
        // 判断是否越界
        if (i < 0 || i >= rows || j < 0 || j >= cols) {
            return 0;
        }
        // 判断是否有障碍物
        if (grid[i][j] == -1) {
            return 0;
        }
        // 到达终点
        if (grid[i][j] == 2) {
            // 判断是否通过所有的无障碍方格
            if (stepCnt == 0) {
                return 1;
            } else {
                return 0;
            }
        }
        // 当前位置标记为障碍物
        grid[i][j] = -1;
        int res = 0;
        // 向上、下、左、右移动，深度搜索
        res += dfs(grid, i - 1, j, stepCnt - 1);
        res += dfs(grid, i + 1, j, stepCnt - 1);
        res += dfs(grid, i, j - 1, stepCnt - 1);
        res += dfs(grid, i, j + 1, stepCnt - 1);
        // 还原障碍物为 0
        grid[i][j] = 0;
        return res;
    }
}

